{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Islands II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #union-find #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #并查集 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numIslands2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #岛屿数量 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个大小为 <code>m x n</code> 的二进制网格 <code>grid</code> 。网格表示一个地图，其中，<code>0</code> 表示水，<code>1</code> 表示陆地。最初，<code>grid</code> 中的所有单元格都是水单元格（即，所有单元格都是 <code>0</code>）。</p>\n",
    "\n",
    "<p>可以通过执行 <code>addLand</code> 操作，将某个位置的水转换成陆地。给你一个数组 <code>positions</code> ，其中 <code>positions[i] = [r<sub>i</sub>, c<sub>i</sub>]</code> 是要执行第 <code>i</code> 次操作的位置 <code>(r<sub>i</sub>, c<sub>i</sub>)</code> 。</p>\n",
    "\n",
    "<p>返回一个整数数组 <code>answer</code> ，其中 <code>answer[i]</code> 是将单元格 <code>(r<sub>i</sub>, c<sub>i</sub>)</code> 转换为陆地后，地图中岛屿的数量。</p>\n",
    "\n",
    "<p><strong>岛屿</strong> 的定义是被「水」包围的「陆地」，通过水平方向或者垂直方向上相邻的陆地连接而成。你可以假设地图网格的四边均被无边无际的「水」所包围。</p>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/10/tmp-grid.jpg\" style=\"width: 500px; height: 294px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]]\n",
    "<strong>输出：</strong>[1,1,2,3]\n",
    "<strong>解释：</strong>\n",
    "起初，二维网格&nbsp;<code>grid</code>&nbsp;被全部注入「水」。（0 代表「水」，1 代表「陆地」）\n",
    "- 操作&nbsp;#1：<code>addLand(0, 0)</code> 将&nbsp;<code>grid[0][0]</code> 的水变为陆地。此时存在 1 个岛屿。\n",
    "- 操作&nbsp;#2：<code>addLand(0, 1)</code> 将&nbsp;<code>grid[0][1]</code> 的水变为陆地。此时存在 1 个岛屿。\n",
    "- 操作&nbsp;#3：<code>addLand(1, 2)</code> 将&nbsp;<code>grid[1][2]</code> 的水变为陆地。此时存在 2 个岛屿。\n",
    "- 操作&nbsp;#4：<code>addLand(2, 1)</code> 将&nbsp;<code>grid[2][1]</code> 的水变为陆地。此时存在 3 个岛屿。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>m = 1, n = 1, positions = [[0,0]]\n",
    "<strong>输出：</strong>[1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= m, n, positions.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= m * n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>positions[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= r<sub>i</sub> &lt; m</code></li>\n",
    "\t<li><code>0 &lt;= c<sub>i</sub> &lt; n</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>你可以设计一个时间复杂度 <code>O(k log(mn))</code> 的算法解决此问题吗？（其中 <code>k == positions.length</code>）</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-islands-ii](https://leetcode.cn/problems/number-of-islands-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-islands-ii](https://leetcode.cn/problems/number-of-islands-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n3\\n[[0,0],[0,1],[1,2],[2,1]]', '1\\n1\\n[[0,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        def find(node):\n",
    "            while parent[node] != parent[parent[node]]:\n",
    "                parent[node] = parent[parent[node]]\n",
    "            return parent[node]\n",
    "        def union(n1, n2):\n",
    "            parent[find(n1)] = find(n2)\n",
    "        \n",
    "        res = [0]*len(positions)\n",
    "        parent = [i for i in range(m*n)]\n",
    "        land = [0 for i in range(m*n)]\n",
    "        for i, (r,c) in enumerate(positions):\n",
    "            idx = r*n + c \n",
    "            if land[idx]:\n",
    "                res[i] = res[i-1]\n",
    "                continue\n",
    "            land[idx] = 1\n",
    "            res[i] = res[i-1] + 1\n",
    "            for dx, dy in [(1,0), (0,1), (0,-1), (-1,0)]:\n",
    "                x, y = r+dx, c+dy\n",
    "                if m>x>=0<=y<n and land[x*n+y]==1 and find(idx)!=find(x*n+y):\n",
    "                    union(idx,x*n+y)\n",
    "                    res[i]-=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, m, n):  \n",
    "        self.parent = list(range(m * n))\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        self.parent[self.find(x)] = self.find(y)\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        uf = UnionFind(m, n)\n",
    "        island = [[0 for j in range(n)] for i in range(m)]\n",
    "        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        res = []\n",
    "        count = 0\n",
    "        for i, j in positions:\n",
    "            if island[i][j]:\n",
    "                res.append(count)\n",
    "                continue\n",
    "            island[i][j] = 1\n",
    "            count += 1\n",
    "            root1 = uf.find(i * n + j)\n",
    "            for dx, dy in directions:\n",
    "                x = i + dx\n",
    "                y = j + dy\n",
    "                if 0 <= x < m and 0 <= y < n and island[x][y]:\n",
    "                    root2 = uf.find(x * n + y)\n",
    "                    if root1 != root2:\n",
    "                        # 先root2后root1，否则root1在union之后会变\n",
    "                        uf.union(root2, root1)\n",
    "                        count -= 1\n",
    "            res.append(count)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # Union find. Time O(k*alpha(mn)) Space O(m*n)\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        dirs = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "        dsu = DSU(m * n)\n",
    "        lands = set()\n",
    "        res = []\n",
    "        for x, y in positions:\n",
    "            # if land already added, just repeat the last answer\n",
    "            if (x, y) in lands:\n",
    "                res.append(res[-1])\n",
    "                continue\n",
    "            lands.add((x, y))\n",
    "            last = res[-1] if res else 0\n",
    "            ancestors = set()\n",
    "            for dx, dy in dirs:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < m and 0 <= ny < n and (nx, ny) in lands:\n",
    "                    ancestors.add(dsu.find(nx * n + ny)) \n",
    "                    dsu.union(x * n + y, nx * n + ny)\n",
    "            # len(ancestors) groups are merged into 1 group\n",
    "            # so the number of islands is deducted by (len(ancestors) - 1)\n",
    "            res.append(last - (len(ancestors) - 1))\n",
    "        return res\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, n):\n",
    "        self.pa = list(range(n))\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.pa[x] != x:\n",
    "            self.pa[x] = self.find(self.pa[x])\n",
    "        return self.pa[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        self.pa[self.find(x)] = self.find(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "\n",
    "\n",
    "        def find(x):\n",
    "            while parent[x]!=x:\n",
    "                y = parent[parent[x]]\n",
    "                parent[x] = y \n",
    "                x = y \n",
    "            return x \n",
    "        \n",
    "\n",
    "        def union(x,y):\n",
    "            p,q = find(x),find(y)\n",
    "            if p!=q:\n",
    "                if p>q:\n",
    "                    p,q = q,p \n",
    "                parent[q] = p \n",
    "            return \n",
    "\n",
    "        n1 = len(positions)\n",
    "        res = [0]*n1 \n",
    "        parent = [-1]*(m*n) \n",
    "        visited = set()\n",
    "\n",
    "        for i in range(n1):\n",
    "            x,y = positions[i]\n",
    "            z = x*n+y\n",
    "            parent[z] = z \n",
    "            if z in visited:\n",
    "                res[i] = res[i-1]\n",
    "                continue \n",
    "            res[i] = res[i-1]+1\n",
    "            \n",
    "\n",
    "            visited.add(z)\n",
    "\n",
    "            for dx,dy in [(1,0),(0,1),(-1,0),(0,-1)]:\n",
    "                if 0<=x+dx<m and 0<=y+dy<n and (x+dx)*n+y+dy in visited:\n",
    "                    if find(z)!=find((x+dx)*n+y+dy):\n",
    "                        union(z,(x+dx)*n+y+dy) \n",
    "                        res[i] -= 1\n",
    "        return res\n",
    "                    \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFindSet(object):\n",
    "    def __init__(self, data_list):\n",
    "        # initialize two dicts, one save the fathers of the nodes,\n",
    "        # the other save the size of the father node \n",
    "        # when initialization, the father of each node is itself \n",
    "        # all the sizes are set to be 1\n",
    "\n",
    "        self.father_dict = {}\n",
    "        self.size_dict = {}\n",
    "\n",
    "        for node in data_list:\n",
    "            self.father_dict[node] = node\n",
    "            self.size_dict[node] = 1\n",
    "\n",
    "    def find(self, node):\n",
    "        # use recursive way to search the root of the node \n",
    "        # when searching, put the node directly points to its root to let the tree shorter\n",
    "\n",
    "        father = self.father_dict[node]\n",
    "        if(node != father):\n",
    "            if father != self.father_dict[father]:    \n",
    "                # when optimize the tree, make sure the size of the father dict is corrcet \n",
    "                self.size_dict[father] -= 1\n",
    "            father = self.find(father)\n",
    "        self.father_dict[node] = father\n",
    "        return father\n",
    "\n",
    "    def is_same_set(self, node_a, node_b):\n",
    "        # set whether two nodes are in the same set, check whether the roots are the same\n",
    "        return self.find(node_a) == self.find(node_b)\n",
    "\n",
    "    def union(self, node_a, node_b):\n",
    "        # combine two sets \n",
    "        if node_a is None or node_b is None:\n",
    "            return\n",
    "\n",
    "        a_head = self.find(node_a)\n",
    "        b_head = self.find(node_b)\n",
    "\n",
    "        if(a_head != b_head):\n",
    "            a_set_size = self.size_dict[a_head]\n",
    "            b_set_size = self.size_dict[b_head]\n",
    "            if(a_set_size >= b_set_size):\n",
    "                self.father_dict[b_head] = a_head\n",
    "                self.size_dict[a_head] = a_set_size + b_set_size\n",
    "            else:\n",
    "                self.father_dict[a_head] = b_head\n",
    "                self.size_dict[b_head] = a_set_size + b_set_size\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        board = [[0] * n for _ in range(m)] \n",
    "        ufs = UnionFindSet(list(range(m*n)))\n",
    "\n",
    "        res = []\n",
    "        cur = 0 \n",
    "        for x, y in positions:\n",
    "            if board[x][y] == 1:\n",
    "                res.append(cur)\n",
    "            else:\n",
    "                board[x][y] = 1 \n",
    "                cur+=1 \n",
    "                if 0<=x+1<m and 0<=y<n and board[x+1][y]==1 and not ufs.is_same_set(x*n + y, (x+1)*n + y):\n",
    "                    ufs.union(x*n + y, (x+1)*n + y)\n",
    "                    cur -= 1\n",
    "                    \n",
    "                    \n",
    "                if 0<=x-1<m and 0<=y<n and board[x-1][y]==1 and not ufs.is_same_set(x*n + y, (x-1)*n + y):\n",
    "                    ufs.union(x*n + y, (x-1)*n + y)\n",
    "                    cur-=1\n",
    "\n",
    "                if 0<=x<m and 0<=y+1<n and board[x][y+1]==1 and not ufs.is_same_set(x*n + y, x*n + y+1):\n",
    "                    ufs.union(x*n + y, x*n + y+1)\n",
    "                    cur-=1 \n",
    "\n",
    "                if 0<=x<m and 0<=y-1<n and board[x][y-1]==1 and not ufs.is_same_set(x*n + y, x*n + y-1):\n",
    "                    ufs.union(x*n + y, x*n + y-1)\n",
    "                    cur-=1 \n",
    "                \n",
    "                res.append(cur)\n",
    "        \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "\n",
    "        root = list(range(m * n))\n",
    "        rks = [0] * (m * n)\n",
    "\n",
    "        self.cnt = 0\n",
    "\n",
    "        def find(x):\n",
    "            if root[x] != x:\n",
    "                root[x] = find(root[x])\n",
    "            return root[x]\n",
    "        \n",
    "        def connect(x, y):\n",
    "            r1, r2 = find(x), find(y)\n",
    "            if r1 != r2:\n",
    "                if rks[r1] > rks[r2]:\n",
    "                    root[r2] = r1\n",
    "                elif rks[r1] < rks[r2]:\n",
    "                    root[r1] = r2\n",
    "                else:\n",
    "                    root[r1] = r2\n",
    "                    rks[r2] += 1\n",
    "                self.cnt += 1\n",
    "        \n",
    "        res = []\n",
    "        nn = 0\n",
    "        seen = set([])\n",
    "        for x, y in positions:\n",
    "            curr_p = x * n + y\n",
    "            nn += curr_p not in seen\n",
    "            seen.add(curr_p)\n",
    "            for nx, ny in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:\n",
    "                prev_p = nx * n + ny\n",
    "                if 0 <= nx < m and 0 <= ny < n and prev_p in seen:\n",
    "                    connect(curr_p, prev_p)\n",
    "            res.append(nn - self.cnt)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        dc, res, sm, POS = {}, [], 0, ((0, 1), (1, 0), (0, -1), (-1, 0))\n",
    "        def find(x):\n",
    "            if dc[x]!=x: dc[x] = find(dc[x])\n",
    "            return dc[x]\n",
    "        for x,y in positions:\n",
    "            key = (x,y)\n",
    "            if key not in dc:\n",
    "                lis = set()\n",
    "                for dx, dy in POS:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if 0 <= nx < m and 0 <= ny < n and (nx,ny) in dc: lis.add(find((nx,ny)))\n",
    "                if lis:\n",
    "                    fkey = lis.pop()\n",
    "                    for nkey in lis: dc[nkey], sm = fkey, sm - 1\n",
    "                    dc[key] = fkey\n",
    "                else: dc[key], sm = key, sm + 1\n",
    "            res.append(sm)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        fa=collections.defaultdict()\n",
    "        grid=[[0 for _ in range(n)]for _ in range(m)]\n",
    "        d=[[0,1],[1,0],[0,-1],[-1,0]]\n",
    "        def find(x):\n",
    "            if x not in fa:\n",
    "                fa[x]=x\n",
    "                return x\n",
    "            if fa[x]==x:\n",
    "                return x\n",
    "            fa[x]=find(fa[x])\n",
    "            return fa[x]\n",
    "        def union(a,b):\n",
    "            if find(a)!=find(b):\n",
    "                fa[find(a)]=find(b)\n",
    "        ls=[]\n",
    "        for a,b in positions:\n",
    "            if grid[a][b]==1:\n",
    "                ls.append(ls[-1])\n",
    "                continue\n",
    "            if ls:\n",
    "                ls.append(ls[-1]+1)\n",
    "            else:\n",
    "                ls.append(1)\n",
    "            #print(ls)\n",
    "            grid[a][b]=1\n",
    "            find((a,b))\n",
    "            for d1,d2 in d:\n",
    "                aa,bb=a+d1,b+d2\n",
    "                if 0<=aa<m and 0<=bb<n:\n",
    "                    if grid[aa][bb]==1:\n",
    "                        if find((aa,bb))!=find((a,b)):\n",
    "                            union((a,b),(aa,bb))\n",
    "                            ls[-1]-=1\n",
    "        return ls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self.num_island = 0\n",
    "        self.parent = {}\n",
    "\n",
    "    def add(self, x):\n",
    "        if x not in self.parent:\n",
    "            self.parent[x] = None\n",
    "            self.num_island += 1\n",
    "        \n",
    "    def find(self, x):\n",
    "        root = x\n",
    "        while self.parent[root] != None:\n",
    "            root = self.parent[root]\n",
    "        while x != root:\n",
    "            origin_par = self.parent[x]\n",
    "            self.parent[x] = root\n",
    "            x = origin_par\n",
    "        return root\n",
    "            \n",
    "    def merge(self, x, y):\n",
    "        root_x, root_y = self.find(x), self.find(y)\n",
    "        if root_x != root_y:\n",
    "            self.parent[root_x] = root_y\n",
    "            self.num_island -= 1\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        self.res = []\n",
    "        uf = UnionFind()\n",
    "        row_record = collections.defaultdict(list)\n",
    "        column_record = collections.defaultdict(list)\n",
    "        for position in positions:\n",
    "            position_tuple = tuple(position)\n",
    "            uf.add(position_tuple)\n",
    "            for item in row_record[position[0]]:\n",
    "                if abs(item[1]-position[1]) == 1:\n",
    "                    uf.merge(item, position_tuple)\n",
    "            for item in column_record[position[1]]:\n",
    "                if abs(item[0]-position[0]) == 1:\n",
    "                    uf.merge(item, position_tuple)\n",
    "\n",
    "            row_record[position[0]].append(position_tuple)\n",
    "            column_record[position[1]].append(position_tuple)\n",
    "            self.res.append(uf.num_island)\n",
    "        return self.res\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        uf = UnionFind()\n",
    "        seen = set()\n",
    "        ans,count = [],0\n",
    "        for x,y in positions:\n",
    "            if (x,y) in seen:\n",
    "                ans.append(count)\n",
    "            else:\n",
    "                uf.add((x,y))\n",
    "                count += 1\n",
    "                seen.add((x,y))\n",
    "                for nx,ny in (x + 1,y),(x - 1,y),(x,y - 1),(x,y + 1):\n",
    "                    if 0 <= nx < m and 0 <= ny < n and (nx,ny) in seen:\n",
    "                        if not uf.is_connected((x,y), (nx,ny)):\n",
    "                            uf.union((x,y),(nx,ny))\n",
    "                            count -= 1\n",
    "                ans.append(count)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        \"\"\"\n",
    "        记录每个节点的父节点\n",
    "        \"\"\"\n",
    "        self.father = {}\n",
    "        self.rank = defaultdict(int)\n",
    "\n",
    "    def find(self, x):\n",
    "        \"\"\"\n",
    "        查找根节点\n",
    "        路径压缩\n",
    "        \"\"\"\n",
    "        if self.father[x] != x:\n",
    "            self.father[x] = self.find(self.father[x])\n",
    "        return self.father[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        \"\"\"\n",
    "        合并两个节点\n",
    "        \"\"\"\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x != y:\n",
    "            if self.rank[x] < self.rank[y]:\n",
    "                self.father[x] = y\n",
    "            else:\n",
    "                self.father[y] = x\n",
    "                if self.rank[x] == self.rank[y]:\n",
    "                    self.rank[x] += 1\n",
    "\n",
    "    def is_connected(self, x, y):\n",
    "        \"\"\"\n",
    "        判断两节点是否相连\n",
    "        \"\"\"\n",
    "        return self.find(x) == self.find(y)\n",
    "\n",
    "    def add(self, x):\n",
    "        \"\"\"\n",
    "        添加新节点\n",
    "        \"\"\"\n",
    "        if x not in self.father:\n",
    "            self.father[x] = x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        self.cnt={}\n",
    "        res=0\n",
    "        ress=[]\n",
    "        present=0\n",
    "        for r,c in positions:\n",
    "            # print(\"CNT\",self.cnt)\n",
    "            pos=r*100000+c \n",
    "            neibs=self.get_neib(m,n,pos)\n",
    "            # print(\"Neib\",r,c,neibs,pos)\n",
    "            mark=[]\n",
    "            for k,v in self.cnt.items():\n",
    "                if pos in v:\n",
    "                    mark.append(k)\n",
    "            if len(mark)!=0:\n",
    "                for index in range(1,len(mark)):\n",
    "                    res-=1\n",
    "                    mk=mark[index]\n",
    "                    self.cnt[mark[0]]|=self.cnt[mk]\n",
    "                    self.cnt.pop(mk)\n",
    "                self.cnt[mark[0]]|=set(neibs)\n",
    "                self.cnt[mark[0]].add(pos)\n",
    "                ress.append(res)\n",
    "            else:\n",
    "                res+=1\n",
    "                self.cnt[present]=set(neibs)\n",
    "                self.cnt[present].add(pos)\n",
    "                ress.append(res)\n",
    "                present+=1\n",
    "        \n",
    "        return ress \n",
    "\n",
    "    def get_neib(self,m,n,pos):\n",
    "        r=pos//100000\n",
    "        c=pos%100000\n",
    "        next_pos=[]\n",
    "        move=[[-1,0],[1,0],[0,1],[0,-1]]\n",
    "        for mm in move:\n",
    "            next_r=r+mm[0]\n",
    "            next_c=c+mm[1]\n",
    "\n",
    "            if next_r>=0 and next_r<m and next_c>=0 and next_c<n:\n",
    "                neib=next_r*100000+next_c\n",
    "                next_pos.append(neib)\n",
    "        return next_pos\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        choices = [[0, -1], [0, 1], [-1, 0], [1, 0]]\n",
    "        parent = [[(i, j) for j in range(n)] for i in range(m)]\n",
    "\n",
    "        def find(i1, j1):\n",
    "            if parent[i1][j1] != (i1, j1):\n",
    "                parent[i1][j1] = find(parent[i1][j1][0], parent[i1][j1][1])\n",
    "            return parent[i1][j1]\n",
    "        \n",
    "        def union(i1, j1, i2, j2):\n",
    "            rep1, rep2 = find(i1, j1), find(i2, j2)\n",
    "            if rep1 != rep2:\n",
    "                parent[rep1[0]][rep1[1]] = rep2\n",
    "        \n",
    "        result = [0]\n",
    "        painted_one_positions = set()\n",
    "        for pos in positions:\n",
    "            if tuple(pos) in painted_one_positions:\n",
    "                result.append(result[-1])\n",
    "                continue\n",
    "\n",
    "            painted_one_positions.add(tuple(pos))\n",
    "            valid_new_poss = []\n",
    "            for c in choices:\n",
    "                new_pos = [pos[0]+c[0], pos[1]+c[1]]\n",
    "                if 0 <= new_pos[0] < m and 0 <= new_pos[1] < n:\n",
    "                    valid_new_poss.append(new_pos)\n",
    "            \n",
    "            one_poss = []\n",
    "            for valid_new_pos in valid_new_poss:\n",
    "                if tuple(valid_new_pos) in painted_one_positions:\n",
    "                    one_poss.append(valid_new_pos)\n",
    "            \n",
    "            if not len(one_poss):\n",
    "                result.append(result[-1]+1)\n",
    "            else:\n",
    "                ones_parents = set()\n",
    "                for one_pos in one_poss:\n",
    "                    ones_parents.add(find(one_pos[0], one_pos[1]))\n",
    "                result.append(result[-1]-(len(ones_parents)-1))\n",
    "                for one_pos in one_poss:\n",
    "                    union(pos[0], pos[1], one_pos[0], one_pos[1])\n",
    "                # compress\n",
    "                # parent = [[find(parent[i][j][0], parent[i][j][1]) for j in range(n)] for i in range(m)]\n",
    "        \n",
    "        return result[1:]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Uset:\n",
    "    def __init__(self, M, N):\n",
    "        self.count = 0\n",
    "        self.parent = {}\n",
    "        self.size = {}\n",
    "        self.data = set()\n",
    "        for i in range(M):\n",
    "            for j in range(N):\n",
    "                self.parent[(i,j)] = (i, j)\n",
    "                self.size[(i, j)] = 1\n",
    "\n",
    "    def register(self, x):\n",
    "        self.data.add(x)\n",
    "        self.count += 1\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        fy = self.find(y)\n",
    "        fx = self.find(x)\n",
    "        if fy != fx:\n",
    "            self.count -= 1\n",
    "            if self.size[fx] <= self.size[fy]:\n",
    "                self.parent[fx] = fy\n",
    "                self.size[fy] += self.size[fx]\n",
    "                self.size[fx] = 0\n",
    "            else:\n",
    "                self.parent[fy] = fx\n",
    "                self.size[fx] += self.size[fy]\n",
    "                self.size[fy] = 0\n",
    "    \n",
    "    def get_count(self):\n",
    "        return self.count\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        num = 1\n",
    "        uset = Uset(m, n)\n",
    "        direc = [-1, 0, 1, 0, -1]\n",
    "        ans = []\n",
    "        for i in range(len(positions)):\n",
    "            pos = tuple(positions[i])\n",
    "            if pos in uset.data:\n",
    "                ans.append(uset.get_count())\n",
    "                continue\n",
    "            uset.register(pos)\n",
    "            for k in range(4):\n",
    "                new_pos = (pos[0] + direc[k], pos[1] + direc[k+1])\n",
    "                if new_pos in uset.data:\n",
    "                    uset.union(new_pos, pos)\n",
    "            ans.append(uset.get_count())\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Uset:\n",
    "    def __init__(self, M, N):\n",
    "        self.count = 0\n",
    "        self.parent = {}\n",
    "        self.size = {}\n",
    "        self.data = set()\n",
    "        for i in range(M):\n",
    "            for j in range(N):\n",
    "                self.parent[(i,j)] = (i, j)\n",
    "                self.size[(i, j)] = 1\n",
    "\n",
    "    def register(self, x):\n",
    "        self.data.add(x)\n",
    "        self.count += 1\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        fy = self.find(y)\n",
    "        fx = self.find(x)\n",
    "        if fy != fx:\n",
    "            self.count -= 1\n",
    "            if self.size[fx] < self.size[fy]:\n",
    "                self.parent[fx] = fy\n",
    "            elif self.size[fx] > self.size[fy]:\n",
    "                self.parent[fy] = fx\n",
    "            else:\n",
    "                self.parent[fx] = fy\n",
    "                self.size[fy] += 1\n",
    "        \n",
    "    \n",
    "    def get_count(self):\n",
    "        return self.count\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        num = 1\n",
    "        uset = Uset(m, n)\n",
    "        direc = [-1, 0, 1, 0, -1]\n",
    "        ans = []\n",
    "        for i in range(len(positions)):\n",
    "            pos = tuple(positions[i])\n",
    "            if pos in uset.data:\n",
    "                ans.append(uset.get_count())\n",
    "                continue\n",
    "            uset.register(pos)\n",
    "            for k in range(4):\n",
    "                new_pos = (pos[0] + direc[k], pos[1] + direc[k+1])\n",
    "                if new_pos in uset.data:\n",
    "                    uset.union(new_pos, pos)\n",
    "            ans.append(uset.get_count())\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        ans = 0\n",
    "        res = []\n",
    "        matrix = [[0] * n for _ in range(m)]\n",
    "\n",
    "        parent={}\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                parent[(i,j)] = (i,j)\n",
    "\n",
    "        def find(p):\n",
    "            if parent[p] != p:\n",
    "                parent[p] = find(parent[p])\n",
    "            return parent[p]\n",
    "\n",
    "        def union(p,q):\n",
    "            if find(p) == find(q):\n",
    "                return False \n",
    "            else:\n",
    "                parent[find(p)] = find(q)\n",
    "                return True\n",
    "\n",
    "        for x,y in positions:\n",
    "            if matrix[x][y] == 1:\n",
    "                res.append(ans)\n",
    "                continue\n",
    "            ans+=1\n",
    "            matrix[x][y] = 1\n",
    "\n",
    "            for i,j in [(0,1), (0,-1), (-1,0), (1,0)]:\n",
    "                xx=x+i \n",
    "                yy=y+j \n",
    "                if m>xx>=0 and n>yy>=0 and matrix[xx][yy] == 1:\n",
    "                    #print(union((xx,yy), (x,y)))\n",
    "                    ans-= union((xx,yy), (x,y))\n",
    "            res.append(ans)\n",
    "\n",
    "        return res\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        added=set() # element: tuple(r,c)\n",
    "        islands=[] # element: set of tuples (r,c)\n",
    "        islands_count=[]\n",
    "        for [r,c] in positions:\n",
    "            if (r,c) not in added:\n",
    "                added.add((r,c))\n",
    "                # 查找可行的邻居位置\n",
    "                neighbors=set()\n",
    "                if r>0:\n",
    "                    neighbors.add((r-1,c))\n",
    "                if c>0:\n",
    "                    neighbors.add((r,c-1))\n",
    "                if r<m-1:\n",
    "                    neighbors.add((r+1,c))\n",
    "                if c<n-1:\n",
    "                    neighbors.add((r,c+1))\n",
    "                # 分离当前岛\n",
    "                new_islands=[] # 不可融合\n",
    "                to_merge=[] # 可融合\n",
    "                for island in islands:\n",
    "                    if len(neighbors.intersection(island))>0:\n",
    "                        to_merge.append(island)\n",
    "                    else:\n",
    "                        new_islands.append(island)\n",
    "                islands=new_islands\n",
    "                # 融合\n",
    "                new_island=set([(r,c)])\n",
    "                for island in to_merge:\n",
    "                    new_island=new_island.union(island)\n",
    "                islands.append(new_island)\n",
    "            islands_count.append(len(islands))\n",
    "        return islands_count\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "\n",
    "        parent = {}\n",
    "\n",
    "        def findRoot(x):\n",
    "            p = parent[x]\n",
    "            if p != x:\n",
    "                parent[x] = findRoot(p)\n",
    "\n",
    "            return parent[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            px, py = findRoot(x), findRoot(y)\n",
    "            if px != py:\n",
    "                parent[px] = py\n",
    "                return False\n",
    "\n",
    "            return True\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                parent[(i, j)] = (i, j)\n",
    "\n",
    "        lands = set()\n",
    "        directions = [0, 1, 0, -1]\n",
    "        count = 0\n",
    "        result = []\n",
    "        for r, c in positions:\n",
    "            if (r, c) not in lands:\n",
    "                count += 1\n",
    "                lands.add((r, c))\n",
    "                for k in range(-1, 3):\n",
    "                    nextR, nextC = r + directions[k], c + directions[k + 1]\n",
    "                    if 0 <= nextR < m and 0 <= nextC < n and (nextR, nextC) in lands:\n",
    "                        if not union((r, c), (nextR, nextC)):\n",
    "                            count -= 1\n",
    "\n",
    "            result.append(count)\n",
    "\n",
    "        # print(parent)\n",
    "        return result\n",
    "                    \n",
    "\n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        parents = {}\n",
    "        offsets = [(0, 1), (1, 0), (-1, 0), (0, -1)]\n",
    "        matrix = [[0] * n for _ in range(m)]\n",
    "\n",
    "        def find(i, j):\n",
    "            if parents[(i, j)] != (i, j):\n",
    "                parents[(i, j)] = find(*parents[(i, j)])\n",
    "            return parents[(i, j)]\n",
    "        \n",
    "        def union(i, j, next_i, next_j):\n",
    "            root_1 = find(i, j)\n",
    "            root_2 = find(next_i, next_j)\n",
    "            if root_1 == root_2:\n",
    "                return False\n",
    "            parents[root_1] = root_2\n",
    "            return True\n",
    "        \n",
    "        ret_list = []\n",
    "        added = set()\n",
    "        nodes = 0\n",
    "        for i, j in positions:\n",
    "            if (i, j) in added:\n",
    "                ret_list.append(ret_list[-1])\n",
    "                continue\n",
    "            added.add((i, j))\n",
    "            nodes += 1\n",
    "            parents[(i, j)] = (i, j)\n",
    "            for offset_i, offset_j in offsets:\n",
    "                next_i = i + offset_i\n",
    "                next_j = j + offset_j\n",
    "                if (next_i, next_j) in added:\n",
    "                    nodes -= union(i, j, next_i, next_j)\n",
    "            ret_list.append(nodes)\n",
    "\n",
    "        return ret_list\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        island = [[0] * n for _ in range(m)]\n",
    "        root = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                root[i][j] = (i, j)\n",
    "        def find(x, y):\n",
    "            if root[x][y] != (x, y):\n",
    "                return find(root[x][y][0], root[x][y][1])\n",
    "            else:\n",
    "                return (x, y)\n",
    "        def union(x1, y1, x2, y2):\n",
    "            p1 = find(x1, y1)\n",
    "            p2 = find(x2, y2)\n",
    "            root[p1[0]][p1[1]] = p2\n",
    "        count = 0\n",
    "        ans = []\n",
    "        for u, v in positions:\n",
    "            if island[u][v] == 1:\n",
    "                ans.append(count)\n",
    "                continue\n",
    "            island[u][v] = 1\n",
    "            s = set([])\n",
    "            if u > 0 and island[u-1][v] == 1:\n",
    "                s.add(find(u-1, v))\n",
    "            if u+1 < m and island[u+1][v] == 1:\n",
    "                s.add(find(u+1, v))\n",
    "            if v > 0 and island[u][v-1] == 1:\n",
    "                s.add(find(u, v-1))\n",
    "            if v+1 < n and island[u][v+1] == 1:\n",
    "                s.add(find(u, v+1))\n",
    "            count = count + 1 - len(s)\n",
    "            ans.append(count)\n",
    "            for p in s:\n",
    "                root[p[0]][p[1]] = (u, v)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        dict = {}\n",
    "        graph = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dict[(i, j)] = (i, j)\n",
    "\n",
    "        def find(a):\n",
    "            if dict[a] == a:\n",
    "                return a\n",
    "            p = dict[a]\n",
    "            newP = find(p)\n",
    "            dict[a] = newP\n",
    "            return newP\n",
    "\n",
    "        count = 0\n",
    "        res = []\n",
    "        for p in positions:\n",
    "            if graph[p[0]][p[1]] == 1:\n",
    "                res.append(count)\n",
    "            else:\n",
    "                graph[p[0]][p[1]] = 1\n",
    "                pl, pr, pu, pd = (-1, -1), (-1, -1), (-1, -1), (-1, -1)\n",
    "                if p[0]-1>=0 and graph[p[0]-1][p[1]] == 1:\n",
    "                    pu = find((p[0]-1, p[1]))\n",
    "                if p[0]+1<m and graph[p[0]+1][p[1]] == 1:\n",
    "                    pd = find((p[0]+1, p[1]))\n",
    "                if p[1]-1>=0 and graph[p[0]][p[1]-1] == 1:\n",
    "                    pl = find((p[0], p[1]-1))\n",
    "                if p[1]+1<n and graph[p[0]][p[1]+1] == 1:\n",
    "                    pr = find((p[0], p[1]+1))\n",
    "                nei = [pl, pr, pu, pd]\n",
    "                distinct = set()\n",
    "                for i in range(4):\n",
    "                    if nei[i] != (-1, -1):\n",
    "                        distinct.add(nei[i])\n",
    "                        dict[nei[i]] = (p[0], p[1])\n",
    "                count = count - len(distinct) + 1\n",
    "                res.append(count)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        parent = {}\n",
    "        ans = []\n",
    "        cnt = 0\n",
    "        matrix = [[0]*n for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                parent[(i,j)] = (i,j)\n",
    "\n",
    "        def find(p):\n",
    "            if parent[p] != p:\n",
    "                parent[p] = find(parent[p])\n",
    "            return parent[p]\n",
    "\n",
    "        def union(p, q):\n",
    "            if find(p) == find(q):\n",
    "                return False \n",
    "            else:\n",
    "                parent[find(p)] = find(q)\n",
    "                return True\n",
    "\n",
    "        for x,y in positions:\n",
    "            if matrix[x][y] ==1:\n",
    "                ans.append(cnt)\n",
    "                continue          ######\n",
    "            matrix[x][y] = 1\n",
    "            cnt +=1\n",
    "            for i, j in [(0,1), (0,-1), (1,0), (-1,0)]:\n",
    "                if 0<=i+x<m and 0<=j+y<n and matrix[i+x][j+y]==1:\n",
    "                    cnt -= union((x,y), (x+i, y+j))                                     ###################\n",
    "            ans.append(cnt)\n",
    "\n",
    "        return ans\n",
    "\n",
    "        #  O(nlog(mn)),  O(mn)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        parent = {}\n",
    "        self.count = 0\n",
    "        ans = []\n",
    "        water = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                parent[(i,j)]=(i,j)\n",
    "        def find(x):\n",
    "            if x!= parent[x]:\n",
    "                parent[x]=find(parent[x])\n",
    "            return parent[x]\n",
    "        def union(x,y):\n",
    "            px = find(x)\n",
    "            py = find(y)\n",
    "            if px!=py:\n",
    "                parent[px]=py\n",
    "                self.count-=1\n",
    "        for r, c in positions:\n",
    "            if (r,c) not in water:\n",
    "                water.add((r,c))\n",
    "                self.count+=1\n",
    "                for nr, nc in (r-1,c),(r+1,c),(r,c-1),(r,c+1):\n",
    "                    if 0<=nr< m and 0<=nc<n and (nr,nc) in water:\n",
    "                        union((r,c), (nr,nc))\n",
    "                ans.append(self.count)\n",
    "            else:\n",
    "                ans.append(ans[-1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        grid = [[0 for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        cur_land = 0\n",
    "        land_list = []\n",
    "        for idx, (i, j) in enumerate(positions):\n",
    "            cur_land += self.op(grid, i, j, idx+1)\n",
    "            land_list.append(cur_land)\n",
    "        return land_list\n",
    "    \n",
    "    def op(self, grid, i, j, cur_id):\n",
    "        if grid[i][j] != 0:\n",
    "            return 0\n",
    "\n",
    "        cur_state = 1\n",
    "        exist_id = float('+inf')\n",
    "        if i > 0 and grid[i-1][j] != 0:\n",
    "            exist_id = min(exist_id, grid[i-1][j])\n",
    "\n",
    "        if i < len(grid)-1 and grid[i+1][j] != 0:\n",
    "            exist_id = min(exist_id, grid[i+1][j])\n",
    "        \n",
    "        if j > 0 and grid[i][j-1] != 0:\n",
    "            exist_id = min(exist_id, grid[i][j-1])\n",
    "        \n",
    "        if j < len(grid[0]) - 1 and grid[i][j+1] != 0:\n",
    "            exist_id = min(exist_id, grid[i][j+1])\n",
    "\n",
    "        if exist_id != float('+inf'):\n",
    "            cur_state -= 1\n",
    "\n",
    "        cur_id = min(exist_id, cur_id)\n",
    "        grid[i][j] = cur_id\n",
    "        if i > 0 and grid[i-1][j] != 0:\n",
    "            if self.run(grid, i-1, j, cur_id):\n",
    "                cur_state -= 1\n",
    "\n",
    "        if i < len(grid)-1 and grid[i+1][j] != 0:\n",
    "            if self.run(grid, i+1, j, cur_id):\n",
    "                cur_state -= 1\n",
    "        \n",
    "        if j > 0 and grid[i][j-1] != 0:\n",
    "            if self.run(grid, i, j-1, cur_id):\n",
    "                cur_state -= 1\n",
    "        \n",
    "        if j < len(grid[0]) - 1 and grid[i][j+1] != 0:\n",
    "            if self.run(grid, i, j+1, cur_id):\n",
    "                cur_state -= 1\n",
    "        return cur_state\n",
    "        \n",
    "    def run(self, grid, i, j, cur_id):\n",
    "        if grid[i][j] == cur_id:\n",
    "            return False\n",
    "        grid[i][j] = cur_id\n",
    "        if i > 0 and grid[i-1][j] > 0:\n",
    "            self.run(grid, i-1, j, cur_id)\n",
    "        if i < len(grid)-1 and grid[i+1][j] > 0:\n",
    "            self.run(grid, i+1, j, cur_id)\n",
    "        if j > 0 and grid[i][j-1] > 0:\n",
    "            self.run(grid, i, j-1, cur_id)\n",
    "        if j < len(grid[0]) - 1 and grid[i][j+1] > 0:\n",
    "            self.run(grid, i, j+1, cur_id)\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        land={}\n",
    "        count=1\n",
    "        ans=[]\n",
    "        def dfs(i,j,tmp):\n",
    "            if not 0<=i<m or not 0<=j<n: return\n",
    "            land[tuple([i,j])]=tmp\n",
    "            if tuple([i-1,j]) in land and land[tuple([i-1,j])]!=tmp:\n",
    "                dfs(i-1,j,tmp)\n",
    "            if tuple([i+1,j]) in land and land[tuple([i+1,j])]!=tmp:\n",
    "                dfs(i+1,j,tmp)\n",
    "            if tuple([i,j-1]) in land and land[tuple([i,j-1])]!=tmp:\n",
    "                dfs(i,j-1,tmp)\n",
    "            if tuple([i,j+1]) in land and land[tuple([i,j+1])]!=tmp:\n",
    "                dfs(i,j+1,tmp)\n",
    "        for i,j in positions:\n",
    "            if tuple([i-1,j]) in land:\n",
    "                tmp=land[tuple([i-1,j])]\n",
    "                dfs(i,j,tmp)\n",
    "            elif tuple([i+1,j]) in land:\n",
    "                tmp=land[tuple([i+1,j])]\n",
    "                dfs(i,j,tmp)\n",
    "            elif tuple([i,j-1]) in land:\n",
    "                tmp=land[tuple([i,j-1])]\n",
    "                dfs(i,j,tmp)\n",
    "            elif tuple([i,j+1]) in land:\n",
    "                tmp=land[tuple([i,j+1])]\n",
    "                dfs(i,j,tmp)\n",
    "            else:\n",
    "                land[tuple([i,j])]=count\n",
    "                count+=1\n",
    "            ans.append(len(set(land.values())))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        islands = 0\n",
    "        grid = [[0] * n for _ in range(m)]\n",
    "        def is_valid(grid, i,j,m,n):\n",
    "            if i >= 0 and i < m and j >= 0 and j < n :\n",
    "                if grid[i][j] != 0:\n",
    "                    return grid[i][j]\n",
    "            return 0\n",
    "            \n",
    "        def dfs(grid,i,j,m,n, target, visited):\n",
    "            if is_valid(grid, i, j, m, n) != 0 and grid[i][j] != 0 and (i, j) not in visited:\n",
    "                grid[i][j] = target\n",
    "                visited.add((i,j))\n",
    "                dfs(grid, i-1, j, m, n, target, visited)\n",
    "                dfs(grid, i+1, j, m, n, target, visited)\n",
    "                dfs(grid, i, j-1, m, n, target, visited)\n",
    "                dfs(grid, i, j+1, m, n, target, visited)\n",
    "\n",
    "        answer = []\n",
    "\n",
    "        for i in positions:\n",
    "            connected = set()\n",
    "            mem = {}\n",
    "            if grid[i[0]][i[1]] != 0:\n",
    "                answer.append(answer[-1])\n",
    "                continue\n",
    "\n",
    "            todos = [(i[0]-1, i[1]), (i[0]+1, i[1]), (i[0], i[1]-1), (i[0], i[1]+1)]\n",
    "            for candidate in todos:\n",
    "                il = is_valid(grid, candidate[0], candidate[1], m, n)\n",
    "                if il != 0:\n",
    "                    connected.add(il)\n",
    "                    if il not in mem:\n",
    "                        mem[il] = (candidate[0], candidate[1])\n",
    "                \n",
    "\n",
    "            if not answer:\n",
    "                grid[i[0]][i[1]] = 1\n",
    "                islands = 1\n",
    "                answer = [1]\n",
    "            elif len(connected) == 0:\n",
    "                islands += 1\n",
    "                grid[i[0]][i[1]] = islands\n",
    "                answer.append(answer[-1] + 1)\n",
    "            elif len(connected) == 1:\n",
    "                grid[i[0]][i[1]] = list(connected)[0]\n",
    "                answer.append(answer[-1])\n",
    "            else:\n",
    "                target = min(connected)\n",
    "                for k, v in mem.items():\n",
    "                    if k != target:\n",
    "                        dfs(grid, v[0], v[1], m, n, target, set())\n",
    "                grid[i[0]][i[1]] = target\n",
    "                answer.append(answer[-1] - len(connected) + 1)\n",
    "\n",
    "\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        matrix = [[0] *n for _ in range(m)]\n",
    "        directions = [[1, 0],[-1, 0],[0, 1],[0, -1]]\n",
    "        ans = [1]\n",
    "        matrix[positions[0][0]][positions[0][1]] = len(positions)\n",
    "\n",
    "        def find(x, y, target):\n",
    "            if x<0 or x==m or y<0 or y==n or matrix[x][y] == 0 or matrix[x][y] ==target:\n",
    "                return\n",
    "            matrix[x][y] = target\n",
    "\n",
    "            for d in  directions:\n",
    "                find(x+d[0],y+d[1], target )\n",
    "\n",
    "        for i in range(1, len(positions)):\n",
    "            x, y, curr = positions[i][0], positions[i][1], ans[-1]\n",
    "            if matrix[x][y] == 0: \n",
    "                for d in  directions:\n",
    "                    if x+d[0]>-1 and x+d[0]<m and y+d[1]>-1 and y+d[1]<n and matrix[x+d[0]][y+d[1]]>0:\n",
    "                        if matrix[x+d[0]][y+d[1]]!=matrix[x][y]:\n",
    "                            if matrix[x][y] == 0:\n",
    "                                matrix[x][y] = matrix[x+d[0]][y+d[1]]\n",
    "                            else:\n",
    "                                curr-=1\n",
    "                                find(x+d[0],y+d[1], matrix[x][y])\n",
    "                \n",
    "                if matrix[x][y] == 0:\n",
    "                    curr+=1\n",
    "                    matrix[x][y] = i\n",
    "            ans.append(curr)\n",
    "            # print(matrix)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        grid = [[0]*n for _ in range(m)]\n",
    "        self.ans = 0\n",
    "        self.nx_color = 1\n",
    "\n",
    "        def union(x, y):\n",
    "            if grid[x][y]:\n",
    "                return self.ans\n",
    "            colors = [grid[i][j] for i, j in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)] if 0 <= i < m and 0 <= j < n and grid[i][j] != 0]\n",
    "            if not colors:\n",
    "                grid[x][y] = self.nx_color\n",
    "                self.nx_color += 1\n",
    "            else:\n",
    "                grid[x][y] = colors[0]\n",
    "                self.ans -= len(set(colors))\n",
    "                color(x, y, colors[0])\n",
    "            self.ans += 1\n",
    "            return self.ans\n",
    "\n",
    "        def color(x, y, c):\n",
    "            for i, j in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:\n",
    "                if 0 <= i < m and 0 <= j < n and grid[i][j] != c and grid[i][j]:\n",
    "                    grid[i][j] = c\n",
    "                    color(i, j, c)\n",
    "\n",
    "        res = [union(*pos) for pos in positions]\n",
    "        return res\n",
    "\n",
    "\"\"\"\n",
    "1 1 0\n",
    "0 0 2\n",
    "0 0 0\n",
    "\"\"\"\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "import numpy as np\n",
    "class Solution(object):\n",
    "\tdef numIslands2(self, m, n, positions):\n",
    "\t\t\"\"\"\n",
    "\t\t:type m: int\n",
    "\t\t:type n: int\n",
    "\t\t:type positions: List[List[int]]\n",
    "\t\t:rtype: List[int]\n",
    "\t\t\"\"\"\n",
    "\t\tgrid = np.zeros([m,n], dtype=np.int)\n",
    "\t\tdirections = [(1,0),(-1,0),(0,-1),(0,1)]\n",
    "\t\t\n",
    "\t\tres = []\n",
    "\t\tindex = 1\n",
    "\t\tisland = collections.defaultdict(set)\n",
    "\t\tfor x,y in positions:\n",
    "\t\t\tif grid[x][y]:\n",
    "\t\t\t\tres.append(len(island))\n",
    "\t\t\t\tcontinue\n",
    "\t\t\t\n",
    "\t\t\taround = []\n",
    "\t\t\tfor dx, dy in directions:\n",
    "\t\t\t\tif 0<=x+dx<m and 0<=y+dy<n:\n",
    "\t\t\t\t\tif grid[x+dx][y+dy] and grid[x+dx][y+dy] not in around:\n",
    "\t\t\t\t\t\taround.append(grid[x+dx][y+dy])\n",
    "\t\t\t\n",
    "\t\t\tif len(around) == 0:\n",
    "\t\t\t\tgrid[x][y] = index\n",
    "\t\t\t\tisland[index].add((x,y))\n",
    "\t\t\t\tindex += 1\n",
    "\t\t\telse:\n",
    "\t\t\t\tmod_index = around[0]\n",
    "\t\t\t\tgrid[x][y] = mod_index\n",
    "\t\t\t\tisland[mod_index].add((x,y))\n",
    "\t\t\t\tfor ori_index in around[1:]:\n",
    "\t\t\t\t\tfor i,j in island[ori_index]:\n",
    "\t\t\t\t\t\tgrid[i][j] = mod_index\n",
    "\t\t\t\t\t\tisland[mod_index].add((i,j))\n",
    "\t\t\t\t\tdel island[ori_index]\n",
    "\t\t\t\n",
    "\t\t\tres.append(len(island))\n",
    "\t\treturn res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        def ajacent(x,y):\n",
    "            ret = []\n",
    "            for offset in [-1,1]:\n",
    "                x_new = x+offset\n",
    "                if x_new < 0 or x_new >= row or array[x_new,y] == 0:\n",
    "                    pass\n",
    "                else:\n",
    "                    ret.append((x_new,y))\n",
    "                y_new = y+offset\n",
    "                if y_new < 0 or y_new >= col or array[x,y_new] == 0:\n",
    "                    pass\n",
    "                else:\n",
    "                    ret.append((x,y_new))\n",
    "            return ret\n",
    "        def find(a):\n",
    "            r_a = a\n",
    "            while father[r_a] != r_a:\n",
    "                r_a = father[r_a]\n",
    "\n",
    "            while father[a] != a:\n",
    "                temp = father[a]\n",
    "                father[temp] = r_a\n",
    "                a = temp\n",
    "            return r_a\n",
    "        def uf(a,b):\n",
    "            root_a = find(a)\n",
    "            root_b = find(b)\n",
    "            if root_a != root_b:\n",
    "                father[root_b] = a\n",
    "                self.count -= 1\n",
    "\n",
    "        def add(x,y):\n",
    "            if array[x,y] == 0:\n",
    "                array[x,y] = 1\n",
    "                self.count += 1\n",
    "                father[(x,y)] = (x,y)\n",
    "                ajacent_land = ajacent(x,y)\n",
    "                for a in ajacent_land:\n",
    "                    uf((x,y), a)\n",
    "            self.res.append(self.count)\n",
    "\n",
    "        array = np.zeros((m,n))\n",
    "        row,col = array.shape\n",
    "        father = {}\n",
    "        self.count = 0\n",
    "        self.res = []\n",
    "        for x,y in positions:\n",
    "            add(x,y)\n",
    "            #print(father)\n",
    "        return self.res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        answer_list = []\n",
    "        now_count = 0\n",
    "        grid = [[(0, 0) for i in range(n+2)] for i in range(m+2)]\n",
    "        for i in range(len(positions)):\n",
    "            positions[i][0] += 1\n",
    "            positions[i][1] += 1\n",
    "        now_island_index = 1\n",
    "        for i in positions:\n",
    "            if grid[i[0]][i[1]] != (0, 0):\n",
    "                answer_list.append(now_count)\n",
    "                continue\n",
    "            flag_no_around = True\n",
    "            for around_i in [(i[0]-1, i[1]),(i[0]+1, i[1]), (i[0], i[1]-1), (i[0], i[1]+1)]:\n",
    "                if grid[around_i[0]][around_i[1]] != (0, 0):\n",
    "                    flag_no_around = False\n",
    "                    if grid[i[0]][i[1]] == (0, 0):\n",
    "                        while around_i != grid[around_i[0]][around_i[1]]:\n",
    "                            around_i = grid[around_i[0]][around_i[1]]\n",
    "                        grid[i[0]][i[1]] = around_i\n",
    "                    else:\n",
    "                        while around_i != grid[around_i[0]][around_i[1]]:\n",
    "                            around_i = grid[around_i[0]][around_i[1]]\n",
    "                        if grid[i[0]][i[1]] == grid[around_i[0]][around_i[1]]:\n",
    "                            continue\n",
    "                        grid[around_i[0]][around_i[1]] = grid[i[0]][i[1]]\n",
    "                        now_count -= 1\n",
    "            if flag_no_around:\n",
    "                grid[i[0]][i[1]] = i\n",
    "                now_count += 1\n",
    "            answer_list.append(now_count)\n",
    "        return answer_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        answer_list = []\n",
    "        now_count = 0\n",
    "        grid = [[0 for i in range(n+2)] for i in range(m+2)]\n",
    "        for i in range(len(positions)):\n",
    "            positions[i][0] += 1\n",
    "            positions[i][1] += 1\n",
    "        print(positions)\n",
    "        print(grid)\n",
    "        now_island_index = 1\n",
    "        for i in positions:\n",
    "            if grid[i[0]][i[1]] != 0:\n",
    "                print('what?')\n",
    "                answer_list.append(now_count)\n",
    "                continue\n",
    "            flag_no_round = True\n",
    "            for j in [(i[0]-1, i[1]), (i[0]+1, i[1]), (i[0], i[1]-1), (i[0], i[1]+1)]:\n",
    "                if grid[j[0]][j[1]] != 0:\n",
    "                    flag_no_round = False\n",
    "                    if grid[i[0]][i[1]] == 0:\n",
    "                        grid[i[0]][i[1]] = grid[j[0]][j[1]]\n",
    "                    else:\n",
    "                        if grid[i[0]][i[1]] == grid[j[0]][j[1]]:\n",
    "                            continue\n",
    "                        else:\n",
    "                            tmp_index = grid[j[0]][j[1]]\n",
    "                            for tmp_i in range(m+2):\n",
    "                                for tmp_j in range(n+2):\n",
    "                                    if grid[tmp_i][tmp_j] == tmp_index:\n",
    "                                        grid[tmp_i][tmp_j] = grid[i[0]][i[1]]\n",
    "                            now_count -= 1\n",
    "            if flag_no_round:\n",
    "                grid[i[0]][i[1]] = now_island_index\n",
    "                now_count += 1\n",
    "                now_island_index += 1\n",
    "            answer_list.append(now_count)\n",
    "        return answer_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        color_positions_dict = {}\n",
    "        answer_list = []\n",
    "        now_count = 0\n",
    "        grid = [[0 for i in range(n+2)] for i in range(m+2)]\n",
    "        grid = [[0 for i in range(n+2)] for i in range(m+2)]\n",
    "        grid = [[0 for i in range(n+2)] for i in range(m+2)]\n",
    "        for i in range(len(positions)):\n",
    "            positions[i][0] += 1\n",
    "            positions[i][1] += 1\n",
    "        now_island_index = 1\n",
    "        for i in positions:\n",
    "            if grid[i[0]][i[1]] != 0:\n",
    "                answer_list.append(now_count)\n",
    "                continue\n",
    "            flag_no_round = True\n",
    "            for j in [(i[0]-1, i[1]), (i[0]+1, i[1]), (i[0], i[1]-1), (i[0], i[1]+1)]:\n",
    "                if grid[j[0]][j[1]] != 0:\n",
    "                    flag_no_round = False\n",
    "                    if grid[i[0]][i[1]] == 0:\n",
    "                        grid[i[0]][i[1]] = grid[j[0]][j[1]]\n",
    "                        color_positions_dict[grid[i[0]][i[1]]].append(i)\n",
    "                    else:\n",
    "                        if grid[i[0]][i[1]] == grid[j[0]][j[1]]:\n",
    "                            continue\n",
    "                        else:\n",
    "                            tmp_index = grid[j[0]][j[1]]\n",
    "                            for tmp_item in color_positions_dict[tmp_index]:\n",
    "                                grid[tmp_item[0]][tmp_item[1]] = grid[i[0]][i[1]]\n",
    "                            color_positions_dict[grid[i[0]][i[1]]] += color_positions_dict.pop(tmp_index)\n",
    "                            now_count -= 1\n",
    "            if flag_no_round:\n",
    "                grid[i[0]][i[1]] = now_island_index\n",
    "                color_positions_dict[now_island_index] = [i]\n",
    "                now_count += 1\n",
    "                now_island_index += 1\n",
    "            answer_list.append(now_count)\n",
    "        return answer_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class listnode:\n",
    "    def __init__(self):\n",
    "        self.next = None\n",
    "        self.island_index = None\n",
    "    \n",
    "class Solution:\n",
    "    def get_four_positions(self, p, m, n):\n",
    "        x = p[0]\n",
    "        y = p[1]\n",
    "        x_arr = [x-1, x+1]\n",
    "        y_arr = [y-1, y+1]\n",
    "        if x == 0:\n",
    "            x_arr[0] = np.nan\n",
    "        if x == m-1:\n",
    "            x_arr[1] = np.nan\n",
    "        if y == 0:\n",
    "            y_arr[0] = np.nan\n",
    "        if y == n-1:\n",
    "            y_arr[1] = np.nan\n",
    "        return ((not np.isnan(x_arr[0]), (x_arr[0], y)), (not np.isnan(x_arr[1]), (x_arr[1], y)), (not np.isnan(y_arr[0]), (x, y_arr[0])), (not np.isnan(y_arr[1]), (x, y_arr[1])))\n",
    "\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        answer = []\n",
    "        p_island_dict = {}\n",
    "        all_record_set = set()\n",
    "        now_island_index = 1\n",
    "        for p_i in positions:\n",
    "            p_i = tuple(p_i)\n",
    "            if p_i in p_island_dict:\n",
    "                answer.append(len(all_record_set))\n",
    "                continue\n",
    "            p_around = self.get_four_positions(p_i, m, n)\n",
    "            flag_no_around = True\n",
    "            for p_around_i in p_around:\n",
    "                if not p_around_i[0]:\n",
    "                    continue\n",
    "                else:\n",
    "                    if p_around_i[1] in p_island_dict:\n",
    "                        flag_no_around = False\n",
    "                        if p_i not in p_island_dict:\n",
    "                            p_island_dict[p_i] = p_island_dict[p_around_i[1]]\n",
    "                        else:\n",
    "                            tmp_p_i = p_island_dict[p_i]\n",
    "                            while tmp_p_i.next != None:\n",
    "                                tmp_p_i = tmp_p_i.next\n",
    "                            tmp_p_around_i = p_island_dict[p_around_i[1]]\n",
    "                            while tmp_p_around_i.next != None:\n",
    "                                tmp_p_around_i = tmp_p_around_i.next\n",
    "                            if tmp_p_i.island_index == tmp_p_around_i.island_index:\n",
    "                                continue\n",
    "                            else:\n",
    "                                all_record_set.remove(tmp_p_around_i.island_index)\n",
    "                                tmp_p_around_i.next = tmp_p_i\n",
    "                                # tmp_node = listnode()\n",
    "                                # tmp_node.island_index = tmp_p_i.island_index\n",
    "                                # tmp_p_i.next = tmp_node\n",
    "                                # tmp_p_around_i.next = tmp_node\n",
    "            if flag_no_around:\n",
    "                tmp_node = listnode()\n",
    "                tmp_node.island_index = now_island_index\n",
    "                p_island_dict[p_i] = tmp_node\n",
    "                all_record_set.add(now_island_index)\n",
    "                now_island_index += 1\n",
    "            answer.append(len(all_record_set))\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "import numpy as np\n",
    "class listnode:\n",
    "    def __init__(self):\n",
    "        self.next = None\n",
    "        self.island_index = None\n",
    "    \n",
    "class Solution:\n",
    "    def get_four_positions(self, p, m, n):\n",
    "        x = p[0]\n",
    "        y = p[1]\n",
    "        x_arr = [x-1, x+1]\n",
    "        y_arr = [y-1, y+1]\n",
    "        if x == 0:\n",
    "            x_arr[0] = np.nan\n",
    "        if x == m-1:\n",
    "            x_arr[1] = np.nan\n",
    "        if y == 0:\n",
    "            y_arr[0] = np.nan\n",
    "        if y == n-1:\n",
    "            y_arr[1] = np.nan\n",
    "        return ((not np.isnan(x_arr[0]), (x_arr[0], y)), (not np.isnan(x_arr[1]), (x_arr[1], y)), (not np.isnan(y_arr[0]), (x, y_arr[0])), (not np.isnan(y_arr[1]), (x, y_arr[1])))\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        max_times = 0\n",
    "        answer = []\n",
    "        p_island_dict = {}\n",
    "        all_record_set = set()\n",
    "        now_island_index = 1\n",
    "        for p_i in positions:\n",
    "            p_i = tuple(p_i)\n",
    "            if p_i in p_island_dict:\n",
    "                answer.append(len(all_record_set))\n",
    "                continue\n",
    "            p_around = self.get_four_positions(p_i, m, n)\n",
    "            flag_no_around = True\n",
    "            for p_around_i in p_around:\n",
    "                if not p_around_i[0]:\n",
    "                    continue\n",
    "                else:\n",
    "                    if p_around_i[1] in p_island_dict:\n",
    "                        flag_no_around = False\n",
    "                        if p_i not in p_island_dict:\n",
    "                            if p_island_dict[p_around_i[1]].next == None:\n",
    "                                p_island_dict[p_i] = p_island_dict[p_around_i[1]]\n",
    "                            else:\n",
    "                                tmp = p_island_dict[p_around_i[1]]\n",
    "                                while tmp.next != None:\n",
    "                                    tmp = tmp.next\n",
    "                                p_island_dict[p_i] = p_island_dict[p_around_i[1]]\n",
    "                                p_island_dict[p_i].next = tmp\n",
    "                        else:\n",
    "                            tmp_p_i = p_island_dict[p_i]\n",
    "                            tmp_times = 0\n",
    "                            while tmp_p_i.next != None:\n",
    "                                tmp_times += 1\n",
    "                                tmp_p_i = tmp_p_i.next\n",
    "                            tmp_p_around_i = p_island_dict[p_around_i[1]]\n",
    "                            while tmp_p_around_i.next != None:\n",
    "                                tmp_times += 1\n",
    "                                tmp_p_around_i = tmp_p_around_i.next\n",
    "                            max_times = tmp_times if tmp_times > max_times else max_times\n",
    "                            if tmp_p_i.island_index == tmp_p_around_i.island_index:\n",
    "                                continue\n",
    "                            else:\n",
    "                                all_record_set.remove(tmp_p_around_i.island_index)\n",
    "                                tmp_p_around_i.next = tmp_p_i\n",
    "                                # tmp_node = listnode()\n",
    "                                # tmp_node.island_index = tmp_p_i.island_index\n",
    "                                # tmp_p_i.next = tmp_node\n",
    "                                # tmp_p_around_i.next = tmp_node\n",
    "            if flag_no_around:\n",
    "                tmp_node = listnode()\n",
    "                tmp_node.island_index = now_island_index\n",
    "                p_island_dict[p_i] = tmp_node\n",
    "                all_record_set.add(now_island_index)\n",
    "                now_island_index += 1\n",
    "            answer.append(len(all_record_set))\n",
    "        # if m == 100:\n",
    "        #     print(max_times)\n",
    "        #     return\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "import numpy as np\n",
    "class listnode:\n",
    "    def __init__(self):\n",
    "        self.next = None\n",
    "        self.island_index = None\n",
    "    \n",
    "class Solution:\n",
    "    def get_four_positions(self, p, m, n):\n",
    "        x = p[0]\n",
    "        y = p[1]\n",
    "        x_arr = [x-1, x+1]\n",
    "        y_arr = [y-1, y+1]\n",
    "        if x == 0:\n",
    "            x_arr[0] = np.nan\n",
    "        if x == m-1:\n",
    "            x_arr[1] = np.nan\n",
    "        if y == 0:\n",
    "            y_arr[0] = np.nan\n",
    "        if y == n-1:\n",
    "            y_arr[1] = np.nan\n",
    "        return ((not np.isnan(x_arr[0]), (x_arr[0], y)), (not np.isnan(x_arr[1]), (x_arr[1], y)), (not np.isnan(y_arr[0]), (x, y_arr[0])), (not np.isnan(y_arr[1]), (x, y_arr[1])))\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        max_times = 0\n",
    "        answer = []\n",
    "        p_island_dict = {}\n",
    "        all_record_set = set()\n",
    "        now_island_index = 1\n",
    "        for p_i in positions:\n",
    "            p_i = tuple(p_i)\n",
    "            if p_i in p_island_dict:\n",
    "                answer.append(len(all_record_set))\n",
    "                continue\n",
    "            p_around = self.get_four_positions(p_i, m, n)\n",
    "            flag_no_around = True\n",
    "            for p_around_i in p_around:\n",
    "                if not p_around_i[0]:\n",
    "                    continue\n",
    "                else:\n",
    "                    if p_around_i[1] in p_island_dict:\n",
    "                        flag_no_around = False\n",
    "                        if p_i not in p_island_dict:\n",
    "                            p_island_dict[p_i] = p_island_dict[p_around_i[1]]\n",
    "                        else:\n",
    "                            tmp_p_i = p_island_dict[p_i]\n",
    "                            tmp_times = 0\n",
    "                            while tmp_p_i.next != None:\n",
    "                                tmp_times += 1\n",
    "                                tmp_p_i = tmp_p_i.next\n",
    "                            tmp_p_around_i = p_island_dict[p_around_i[1]]\n",
    "                            while tmp_p_around_i.next != None:\n",
    "                                tmp_times += 1\n",
    "                                tmp_p_around_i = tmp_p_around_i.next\n",
    "                            max_times = tmp_times if tmp_times > max_times else max_times\n",
    "                            if tmp_p_i.island_index == tmp_p_around_i.island_index:\n",
    "                                continue\n",
    "                            else:\n",
    "                                all_record_set.remove(tmp_p_around_i.island_index)\n",
    "                                tmp_p_around_i.next = tmp_p_i\n",
    "                                # tmp_node = listnode()\n",
    "                                # tmp_node.island_index = tmp_p_i.island_index\n",
    "                                # tmp_p_i.next = tmp_node\n",
    "                                # tmp_p_around_i.next = tmp_node\n",
    "            if flag_no_around:\n",
    "                tmp_node = listnode()\n",
    "                tmp_node.island_index = now_island_index\n",
    "                p_island_dict[p_i] = tmp_node\n",
    "                all_record_set.add(now_island_index)\n",
    "                now_island_index += 1\n",
    "            answer.append(len(all_record_set))\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class listnode:\n",
    "    def __init__(self):\n",
    "        self.next = None\n",
    "        self.island_index = None\n",
    "    \n",
    "class Solution:\n",
    "    def get_four_positions(self, p, m, n):\n",
    "        x = p[0]\n",
    "        y = p[1]\n",
    "        x_arr = [x-1, x+1]\n",
    "        y_arr = [y-1, y+1]\n",
    "        if x == 0:\n",
    "            x_arr[0] = np.nan\n",
    "        if x == m-1:\n",
    "            x_arr[1] = np.nan\n",
    "        if y == 0:\n",
    "            y_arr[0] = np.nan\n",
    "        if y == n-1:\n",
    "            y_arr[1] = np.nan\n",
    "        return ((not np.isnan(x_arr[0]), (x_arr[0], y)), (not np.isnan(x_arr[1]), (x_arr[1], y)), (not np.isnan(y_arr[0]), (x, y_arr[0])), (not np.isnan(y_arr[1]), (x, y_arr[1])))\n",
    "\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        answer = []\n",
    "        p_island_dict = {}\n",
    "        all_record_set = set()\n",
    "        now_island_index = 1\n",
    "        for p_i in positions:\n",
    "            p_i = tuple(p_i)\n",
    "            if p_i in p_island_dict:\n",
    "                answer.append(len(all_record_set))\n",
    "                continue\n",
    "            p_around = self.get_four_positions(p_i, m, n)\n",
    "            flag_no_around = True\n",
    "            for p_around_i in p_around:\n",
    "                if not p_around_i[0]:\n",
    "                    continue\n",
    "                else:\n",
    "                    if p_around_i[1] in p_island_dict:\n",
    "                        flag_no_around = False\n",
    "                        if p_i not in p_island_dict:\n",
    "                            p_island_dict[p_i] = p_island_dict[p_around_i[1]]\n",
    "                        else:\n",
    "                            tmp_p_i = p_island_dict[p_i]\n",
    "                            while tmp_p_i.next != None:\n",
    "                                tmp_p_i = tmp_p_i.next\n",
    "                            tmp_p_around_i = p_island_dict[p_around_i[1]]\n",
    "                            while tmp_p_around_i.next != None:\n",
    "                                tmp_p_around_i = tmp_p_around_i.next\n",
    "                            if tmp_p_i.island_index == tmp_p_around_i.island_index:\n",
    "                                continue\n",
    "                            else:\n",
    "                                all_record_set.remove(tmp_p_around_i.island_index)\n",
    "                                tmp_node = listnode()\n",
    "                                tmp_node.island_index = tmp_p_i.island_index\n",
    "                                tmp_p_i.next = tmp_node\n",
    "                                tmp_p_around_i.next = tmp_node\n",
    "            if flag_no_around:\n",
    "                tmp_node = listnode()\n",
    "                tmp_node.island_index = now_island_index\n",
    "                p_island_dict[p_i] = tmp_node\n",
    "                all_record_set.add(now_island_index)\n",
    "                now_island_index += 1\n",
    "            answer.append(len(all_record_set))\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class listnode:\n",
    "    def __init__(self):\n",
    "        self.next = None\n",
    "        self.island_index = None\n",
    "    \n",
    "class Solution:\n",
    "    def get_four_positions(self, p, m, n):\n",
    "        x = p[0]\n",
    "        y = p[1]\n",
    "        x_arr = [x-1, x+1]\n",
    "        y_arr = [y-1, y+1]\n",
    "        if x == 0:\n",
    "            x_arr[0] = np.nan\n",
    "        if x == m-1:\n",
    "            x_arr[1] = np.nan\n",
    "        if y == 0:\n",
    "            y_arr[0] = np.nan\n",
    "        if y == n-1:\n",
    "            y_arr[1] = np.nan\n",
    "        return ((not np.isnan(x_arr[0]), (x_arr[0], y)), (not np.isnan(x_arr[1]), (x_arr[1], y)), (not np.isnan(y_arr[0]), (x, y_arr[0])), (not np.isnan(y_arr[1]), (x, y_arr[1])))\n",
    "\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        answer = []\n",
    "        p_island_dict = {}\n",
    "        all_record_set = set()\n",
    "        now_island_index = 1\n",
    "        for p_i in positions:\n",
    "            p_i = tuple(p_i)\n",
    "            if p_i in p_island_dict:\n",
    "                answer.append(len(all_record_set))\n",
    "                continue\n",
    "            p_around = self.get_four_positions(p_i, m, n)\n",
    "            flag_no_around = True\n",
    "            for p_around_i in p_around:\n",
    "                if not p_around_i[0]:\n",
    "                    continue\n",
    "                else:\n",
    "                    if p_around_i[1] in p_island_dict:\n",
    "                        flag_no_around = False\n",
    "                        if p_i not in p_island_dict:\n",
    "                            p_island_dict[p_i] = p_island_dict[p_around_i[1]]\n",
    "                        else:\n",
    "                            tmp_p_i = p_island_dict[p_i]\n",
    "                            while tmp_p_i.next != None:\n",
    "                                tmp_p_i = tmp_p_i.next\n",
    "                            tmp_p_around_i = p_island_dict[p_around_i[1]]\n",
    "                            while tmp_p_around_i.next != None:\n",
    "                                tmp_p_around_i = tmp_p_around_i.next\n",
    "                            if tmp_p_i.island_index == tmp_p_around_i.island_index:\n",
    "                                continue\n",
    "                            else:\n",
    "                                all_record_set.remove(tmp_p_around_i.island_index)\n",
    "                                tmp_node = listnode()\n",
    "                                tmp_node.island_index = tmp_p_i.island_index\n",
    "                                tmp_p_i.next = tmp_node\n",
    "                                tmp_p_around_i.next = tmp_node\n",
    "            if flag_no_around:\n",
    "                tmp_node = listnode()\n",
    "                tmp_node.island_index = now_island_index\n",
    "                p_island_dict[p_i] = tmp_node\n",
    "                all_record_set.add(now_island_index)\n",
    "                now_island_index += 1\n",
    "            answer.append(len(all_record_set))\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def get_four_positions(self, p, m, n):\n",
    "        x = p[0]\n",
    "        y = p[1]\n",
    "        x_arr = [x-1, x+1]\n",
    "        y_arr = [y-1, y+1]\n",
    "        if x == 0:\n",
    "            x_arr[0] = np.nan\n",
    "        if x == m-1:\n",
    "            x_arr[1] = np.nan\n",
    "        if y == 0:\n",
    "            y_arr[0] = np.nan\n",
    "        if y == n-1:\n",
    "            y_arr[1] = np.nan\n",
    "        return ((not np.isnan(x_arr[0]), (x_arr[0], y)), (not np.isnan(x_arr[1]), (x_arr[1], y)), (not np.isnan(y_arr[0]), (x, y_arr[0])), (not np.isnan(y_arr[1]), (x, y_arr[1])))\n",
    "\n",
    "    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:\n",
    "        answer = []\n",
    "        set_list = []\n",
    "        all_set = set()\n",
    "        for p_i in positions:\n",
    "            p_i = tuple(p_i)\n",
    "            if p_i in all_set:\n",
    "                answer.append(answer[-1])\n",
    "                continue\n",
    "            p_around = self.get_four_positions(p_i, m, n)\n",
    "            flag_no_around = True\n",
    "            first_added_cat = None\n",
    "            for p_around_i in p_around:\n",
    "                if not p_around_i[0]:\n",
    "                    continue\n",
    "                else:\n",
    "                    if p_around_i[1] in all_set:\n",
    "                        flag_no_around = False\n",
    "                        if p_i not in all_set:\n",
    "                            for set_index in range(len(set_list)):\n",
    "                                if p_around_i[1] in set_list[set_index]:\n",
    "                                    set_list[set_index].add(p_i)\n",
    "                                    all_set.add(p_i)\n",
    "                                    first_added_cat = set_index\n",
    "                                    break\n",
    "                        else:\n",
    "                            for set_index in range(len(set_list)):\n",
    "                                if p_around_i[1] in set_list[set_index]:\n",
    "                                    if p_i in set_list[set_index]:\n",
    "                                        continue\n",
    "                                    else:\n",
    "                                        for set_index_2 in range(len(set_list)):\n",
    "                                            if p_i in set_list[set_index_2]:\n",
    "                                                set_list[set_index] = set_list[set_index].union(set_list[set_index_2])\n",
    "                                                set_list[set_index_2] = set()\n",
    "                                                break\n",
    "                                    break\n",
    "            if flag_no_around:\n",
    "                set_list.append(set())\n",
    "                set_list[-1].add(p_i)\n",
    "                all_set.add(p_i)\n",
    "            while set() in set_list:\n",
    "                set_list.remove(set())\n",
    "            answer.append(len(set_list))\n",
    "        return answer"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
